Conventional distributed database systems store data in a cluster which typically consists of a plurality of database servers. When the data volume in a database system reaches full capacity or a threshold of the capacity of the database system, new computer servers are introduced and added to the database system to store more data. This process of adding new servers to existing servers and making the new database servers to be able to accept more data is generally referred to as horizontal scaling of a distributed database system.
Horizontal scaling in these conventional distributed database systems requires data redistribution among the database servers. That is, a portion of or all of the data that is already stored in the existing database servers is migrated to one or more of the new database servers. This data-exchange process among the servers is costly, time consuming, and requires resources. When the total data volume is large in the system, the migration may take a long time (in hours or days). The scaling process may cause long downtime in a production system.